#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int n = 0, m = 0;
    int ret = 0;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        n = matrix.size();
        m = matrix[0].size();
        vector<vector<int>> check(n, vector<int>(m));
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                ret = max(ret, dfs(matrix, check, i, j));
            }
        }

        return ret;
    }
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& check, int x, int y)
    {
        if (check[x][y])
            return check[x][y];

        int re = 0;
        for (int i = 0; i < 4; ++i)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || tx == n || ty < 0 || ty == m || matrix[tx][ty] >= matrix[x][y])
                continue;
            re = max(re, dfs(matrix, check, tx, ty));
        }
        check[x][y] = re + 1;

        return check[x][y];
    }
};